package primary.code05_Tree;

import java.util.ArrayDeque;
import java.util.Deque;
    import java.util.Stack;

/**
 * leetcode https://leetcode.cn/problems/h54YBf/description/
 *
 * @author Yudi Wang
 * @date 2021/7/13 10:36
 * <p>
 * 二叉树的序列化与反序列化
 */
public class Code10_SerializeBinaryTree {
    /**
     * 递归序列化
     */
    public static StringBuilder serialize(Node head) {
        StringBuilder sb = new StringBuilder();
        if (head == null) return sb.append("#_");
        sb.append(head.data + "_");
        StringBuilder left = serialize(head.left);
        StringBuilder right = serialize(head.right);
        return sb.append(left).append(right);

    }

    /**
     * 递归序列化
     */
    public static void serialize3(Node head, StringBuilder sb) {
        if (head == null) {
            sb.append("#_");
            return;
        }
        sb.append(head.data + "_");
        serialize3(head.left, sb);
        serialize3(head.right, sb);
    }

    /**
     * 循环序列化
     * 前序
     */
    public static StringBuilder serialize2(Node head) {
        StringBuilder sb = new StringBuilder();
        if (head == null) return sb.append("#_");
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                sb.append(cur.data + "_");
                stack.push(cur);
                cur = cur.left;
            }
            sb.append("#_");
            Node push = stack.pop();
            cur = push.right;
        }
        sb.append("#_");//注意，不会进入最后一个空节点
        return sb;
    }

    /**
     * 前序序列化
     *
     * @param head
     * @return
     */
    public static StringBuilder serialize2Test(Node head) {
        StringBuilder s = new StringBuilder();
        if (head == null) return s;
        Node cur = head;
        Stack<Node> stack = new Stack<>();
        stack.push(cur);
        while (!stack.isEmpty()) {
            cur = stack.pop();
            if (cur != null) {
                s.append(cur.data + "_");
            } else {
                s.append("#_");
                continue;
            }
            if (cur.right != null) {
                stack.push(cur.right);
            } else {
                stack.push(null);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            } else {
                stack.push(null);
            }
        }
        return s;
    }

    private static int index = 0;

    public static Node deserialize(String str) {
        if (str == null || str.length() <= 0) return null;
        String[] nodesStr = str.split("_");
        if (nodesStr[index].equals("#")) {
            index++;
            return null;
        } else {
            Node newNode = new Node(Integer.parseInt(nodesStr[index]));
            index++;
            Node left = deserialize(str);
            Node right = deserialize(str);
            newNode.left = left;
            newNode.right = right;
            return newNode;
        }
    }

    private static int idx = 0;

    public static Node deserializeTest(String[] str) {
        //不要再IF条件中++
        if (str[idx].equals("#")) {
            idx++;
            return null;
        }
        Node node = new Node(Integer.parseInt(str[idx++]));
        Node left = deserializeTest(str);
        Node right = deserializeTest(str);
        node.left = left;
        node.right = right;
        return node;
    }


    private static int strIndex = 0;

    /**
     * 前序反序列化
     *
     * @param str
     * @return
     */
    public static Node deserializeTest2(String[] str) {
        if (str == null || str.length == 0 || strIndex >= str.length) return null;
        Node cur = str[strIndex].equals("#") ? null : new Node(Integer.parseInt(str[strIndex]));
        strIndex++;
        if (cur == null) return cur;
        Node left = deserializeTest2(str);
        Node right = deserializeTest2(str);
        cur.left = left;
        cur.right = right;
        return cur;
    }

    public static void inTraversal(Node head) {
        if (head == null) return;
        System.out.print(head.data + "  ");
        inTraversal(head.left);
        inTraversal(head.right);
    }

    public static void main(String[] args) {
        Node head = new Node(4);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.right.left = new Node(7);
        head.right.right = new Node(9);
        head.right.right.right = new Node(10);
        System.out.println(serialize(head));
        System.out.println(serialize2(head));
        System.out.println(serialize2Test(head));
        final StringBuilder res = new StringBuilder();
        serialize3(head, res);
        System.out.println(res);

        System.out.println();
        Node deserializeHead = deserialize("4_3_2_#_#_4_#_#_8_7_#_#_9_#_10_#_#_");
        String s = "4_3_2_#_#_4_#_#_8_7_#_#_9_#_10_#_#_";
        Node deserializeHeadTest = deserializeTest(s.split("_"));
        Node deserializeHeadTest2 = deserializeTest2(s.split("_"));
        inTraversal(deserializeHead);
        System.out.println();
        System.out.println("============");
        inTraversal(deserializeHeadTest);
        System.out.println();
        System.out.println("============");
        inTraversal(deserializeHeadTest2);
    }
}
